package Math;//给定方法 rand7 可生成 [1,7] 范围内的均匀随机整数，试写一个方法 rand10 生成 [1,10] 范围内的均匀随机整数。
//
// 你只能调用 rand7() 且不能调用其他方法。请不要使用系统的 Math.random() 方法。 
//
// 
// 
//
// 每个测试用例将有一个内部参数 n，即你实现的函数 rand10() 在测试时将被调用的次数。请注意，这不是传递给 rand10() 的参数。 
//
// 
//
// 示例 1: 
//
// 
//输入: 1
//输出: [2]
// 
//
// 示例 2: 
//
// 
//输入: 2
//输出: [2,8]
// 
//
// 示例 3: 
//
// 
//输入: 3
//输出: [3,8,10]
// 
//
// 
//
// 提示: 
//
// 
// 1 <= n <= 10⁵ 
// 
//
// 
//
// 进阶: 
//
// 
// rand7()调用次数的 期望值 是多少 ? 
// 你能否尽量少调用 rand7() ? 
// 
// Related Topics 数学 拒绝采样 概率与统计 随机化 👍 391 👎 0


//leetcode submit region begin(Prohibit modification and deletion)

import java.util.Random;

/**
 * The rand7() API is already defined in the parent class SolBase.
 * public int rand7();
 * @return a random integer in the range 1 to 7
 */
class SolBase{

    Random r = new Random();
    /**
     * rand7默认生成随机【1，7】的数
     * */
    int rand7(){
        return r.nextInt(7)+1;
    }

    /**
     * 生成指定范围[1,len]的数
     * */
    int randX(int len){
        return r.nextInt(len);
    }
}


class rand10 extends SolBase {
    /**
     * 本质上，需要利用已有的randX函数，等概率生成一个范围包含要求的randY的数据范围
     * 比如利用randX等概率的生成 [1,X^2]的范围，那Y在这个范围内，那么只要抛弃大于Y的即满足等概率生成
     *
     * 基于这样一个事实 (randX() - 1)* Y + randY() 可以等概率的生成[1, X * Y]范围的随机数
     * randX()的范围[1, X]，randx()-1的范围就是[0, X-1]。
     * (randx() - 1) * Y的范围是[0, (X-1)*Y]，
     * (randx() - 1) * Y + randY()的范围自然就是[1, X * Y]
     * */
    public int rand10() {
        int row, col, idx;
        do{
            row = rand7();
            col = rand7();
            idx = (row-1) * 7 + col;
        }while(idx>40);

        return (idx-1)%10+1;
        
    }

    public static void main(String[] args) {
        rand10 rand10 = new rand10();
        for (int i = 0; i < 100; i++) {
            System.out.println(rand10.rand10());
        }
    }
}


//leetcode submit region end(Prohibit modification and deletion)
